{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 线性秘密共享方案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from node import *\n",
    "from queue import Queue\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "示例t,n门限 \\\n",
    "![](../imgs/lsss_tn.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lewko-Waters算法\n",
    "算法中对访问控制树有一定的要求，它的非叶子节点是AND或OR门限，叶子节点是属性。更严格来说处理的访问控制树可以使用单调（排除NOT门限）布尔公式来表达。引言中的例子改写为布尔表达式如下：\n",
    "$$\n",
    "E\\land \\left( \\left( A\\land B \\right) \\lor \\left( A\\land C \\right) \\lor \\left( A\\land D \\right) \\lor \\left( B\\land C \\right) \\lor \\left( B\\land D \\right) \\lor \\left( C\\land D \\right) \\right)\n",
    "$$\n",
    "对应的访问树如下\n",
    "![布尔访问树](../imgs/bool_lsss_tn.png)\n",
    "在算法开始阶段，将树的根节点标注一个长度为1的向量(1)，初始化一个全局变量counter=1。并按照如下算法进行广度优先遍历：\n",
    "\n",
    "1. 如果父节点是一个标注着向量$ \\lor  $的OR门限\n",
    "   1. 那么将它的两个子节点标注为v\n",
    "   2. 保持counter不变。\n",
    "2. 如果父节点是一个标注着向量$ \\land  $的AND门限\n",
    "   1. 将v的末尾用0填充，使得v的长度变为counter\n",
    "   2. 右子节点用v||1标注（||表示连接符号）\n",
    "   3. 左子节点用(0,...,0)||-1标注（0的个数为counter）\n",
    "   4. counter的值增加1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0]\n",
      " [ 1  1  0  1  0]\n",
      " [ 0  0  0  0 -1]\n",
      " [ 1  1  0  0  1]\n",
      " [ 0  0 -1  0  0]\n",
      " [ 0  0 -1  0  0]\n",
      " [ 1  1  1  0  0]\n",
      " [ 1  1  1  0  0]]\n"
     ]
    }
   ],
   "source": [
    "# 构建上述布尔访问树, and节点使用门限(2, 2)表示，or节点使用(1, 2)表示\n",
    "root = Node.threshold_node(Gate(2, 2), [\n",
    "    Node.attr_node('E'),\n",
    "    Node.threshold_node(Gate(1, 2), [\n",
    "        Node.threshold_node(Gate(1, 2), [\n",
    "            Node.threshold_node(Gate(2, 2), [Node.attr_node('A'), Node.attr_node('B')]),\n",
    "            Node.threshold_node(Gate(2, 2), [Node.attr_node('C'), Node.attr_node('D')])\n",
    "        ]),\n",
    "        Node.threshold_node(Gate(2, 2), [\n",
    "            Node.threshold_node(Gate(1, 2), [Node.attr_node('A'), Node.attr_node('B')]),\n",
    "            Node.threshold_node(Gate(1, 2), [Node.attr_node('C'), Node.attr_node('D')])\n",
    "        ])\n",
    "    ])\n",
    "])\n",
    "\n",
    "# print(root)\n",
    "\n",
    "# 布尔访问树转LSSS访问矩阵\n",
    "def booltree2lsss(root: Node):\n",
    "    c, max_len, m = 1, 1, []\n",
    "    q = Queue()\n",
    "    root.attr = [1]\n",
    "    q.put(root)\n",
    "    while not q.empty():\n",
    "        tmp = q.get()\n",
    "        v = tmp.attr\n",
    "        max_len = max(max_len, len(v))\n",
    "        if tmp.is_leaf():\n",
    "            m.append(tmp.attr)\n",
    "            continue\n",
    "        lc, rc = tmp.children[0], tmp.children[1]\n",
    "        if tmp.gate.k == 1:\n",
    "            lc.attr = v\n",
    "            rc.attr = v\n",
    "        else:\n",
    "            v += [0] * (c - len(v))\n",
    "            lc.attr = [0] * c + [-1]\n",
    "            rc.attr = v + [1]\n",
    "            c += 1\n",
    "        q.put(lc)\n",
    "        q.put(rc)\n",
    "    for row in m:\n",
    "        row += [0] * (max_len - len(row))\n",
    "    return m\n",
    "\n",
    "matrix = booltree2lsss(root)\n",
    "darray = np.array(matrix)\n",
    "print(darray)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献\n",
    "1. [线性秘密共享方案（LSSS）矩阵的构造](https://blog.csdn.net/qq_36291381/article/details/109703720)\n",
    "2. [基于LSSS的CPABE](https://www.bilibili.com/video/BV1BS4y1o7E8?spm_id_from=333.337.search-card.all.click&vd_source=37ca2b59d228ac30edfe589963b7a65b)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.9 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "e5030792b3492f6b12d94f1f48beca3d8e59ec05fd59d0aaaa48e684281ed297"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
